package NC6_二叉树中的最大路径和;

class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
}

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int maxSum = 0;
    public int maxPathSum (TreeNode root) {
        // write code here
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        int priceNewPath = node.val + leftGain + rightGain;

        maxSum = Math.max(maxSum, priceNewPath);

        return node.val + Math.max(leftGain, rightGain);
    }
}